package com.wyw.leetcode.learning.simple;

import com.wyw.leetcode.simple.parent.ListNode;

/**
 * leetcode topic 21
 *  合并两个有序链表
 *      将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 * @Author Mr Wu （yewen.wu.china@gmail.com）
 * @Date 2021/12/22 14:52
 */
public class Topic021 {

    public static void main(String[] args) {
        ListNode listNode1 = null;
        for(int i=7; i > 1; i--) {
            ListNode listNodeNew = new ListNode(2 * i);
            listNodeNew.next = listNode1;
            listNode1 = listNodeNew;
        }

        ListNode listNode2 = null;
        for(int i=6; i>1; i--) {
            ListNode listNodeNew = new ListNode(3 * i);
            listNodeNew.next = listNode2;
            listNode2 = listNodeNew;
        }

        ListNode listNode = mergeTwoLists1(listNode1, listNode2);
        System.out.println("end");

    }
    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null ) return list2;
        if(list2 == null ) return list1;
        ListNode result = list1.val < list2.val ? list1 : list2;
        result.next = mergeTwoLists(result.next, list1.val >= list2.val ? list1 : list2);
        return result;
    }

    /**
     * 迭代
     */
    public static ListNode mergeTwoLists1(ListNode list1, ListNode list2) {
        ListNode listNode = new ListNode(-1);
        ListNode result = listNode;
        while(list1!= null && list2!=null) {
            if(list1.val < list2.val) {
                result.next = list1;
                list1 = list1.next;
            } else {
                result.next = list2;
                list2 = list2.next;
            }
            result = result.next;

        }
        result.next = list1==null?list2:list1;
        return listNode.next;
    }
}

